package lt260


/*  lt136
260. 只出现一次的数字 III
给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。
 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。
进阶：你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？

区别，136只出现一次的元素只出现了一次
*/

/*
我们可以使用位运算x & -x 取出 x 的二进制表示中最低位那个 1，设其为第 l 位，那x 1和 x2
​中的某一个数的二进制表示的第 l 位为 0，另一个数的二进制表示的第 l 位为 1。
在这种情况下，x1⊕x2的二进制表示的第 ll 位才能为 1。

这样一来，我们就可以把nums中的所有元素分成两类，
其中一类包含所有二进制表示的第 l 位为 0 的数，另一类包含所有二进制表示的第 l 位为 1 的数。
可以发现：
    对于任意一个在数组 nums 中出现两次的元素，该元素的两次出现会被包含在同一类中；
    对于任意一个在数组 nums 中只出现了一次的元素，即x1和x2，它们会被包含在不同类中。

因此，如果我们将每一类的元素全部异或起来，那么其中一类会得到 x1，另一类会得到 x2。
这样我们就找出了这两个只出现一次的元素。
*/
func singleNumber(nums []int) []int {
    xorSum := 0
    for _, num := range nums {
        xorSum ^= num   //两个出现一次的数的异或和
    }
    lsb := xorSum & -xorSum   //得到最低位的1
	// fmt.Printf("lsb=%b\n",lsb)   // lsb = 10    xorSum = 6 = Ox 0110
    type1, type2 := 0, 0
    for _, num := range nums {
        if num&lsb > 0 {  //一类
            type1 ^= num
        } else {
            type2 ^= num
        }
    }
    return []int{type1, type2}
}

